1. FIELD OF THE INVENTION
This invention relates to error detection and, particularly, to a method and apparatus for detecting errors in a data set of sequential binary digits.
2. PRIOR ART STATEMENT
It has been widely recognized that error detection is desirable in situations where a data set of sequential binary digits is operated upon in a manner having a significant probability of inadvertently altering at least one of the binary digits. Accordingly, it is common in systems requiring data transmission/reception or data recording/retrieval to incorporate an error detection scheme selected to provide a desired level of detection at an acceptable cost. For example, simple parity check techniques are generally satisfactory in byte or word oriented, data transmission and storage systems. More sophisticated polynomial or cyclic redundancy code (CRC) techniques have found use in systems which transmit or store relatively long strings of binary digits, due to an inherently lower level of redundancy. For example, the simple CRC technique discussed in "CRC Error-Detection Schemes Ensure Data Accuracy" (Electronic Data News, Sept. 5, 1978, pages 119-123), could be used advantageously in magnetic tape or disk systems or in magnetic bubble memory devices, since such devices generally store and retrieve data in relatively long blocks.
In some applications, an additional advantage may be realized by exploiting the inherent capability of certain of the CRC techniques to correct errors upon detection. See, Peterson and Weldon, Error Correction Codes, MIT Press, 2d. Ed. 1972; and Lin, An Introduction to Error Correction Codes, Prentice-Hall, 1970. Unfortunately, such techniques generally provide correction capability at the expense of detection. For example, one rather conventional CRC technique which has powerful error detection capability but only single bit correction is described in "Understanding Cyclic Redundancy Codes" (Computer Design, November 1975, pages 93-99). In contrast, a special CRC technique, known as the FIRE code, which can correct a burst of up to five consecutive errors, but at a degraded level of detection, is described in "Megabit Bubble Memory Chip Gets Support From LSI Family" (Electronics, Apr. 26, 1979, pages 105-111).